package com.cat.binaryAnswer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/description/
 * @create 2025/8/12 15:26
 * @since JDK17
 */

public class Solution12 {
    static HashSet<Integer> set = new HashSet<>();
    boolean check(int[] nums, int target) {
        int sum = 0;
        for (int r = nums.length - 1, l = r - 1; l >= 0; ) {
            if (set.contains(r)) {
                r--;
                continue;
            }
            if ((nums[l] << 1) <= nums[r]) {
                set.add(l);
                r--;
                sum += 2;
            } else {
                l--;
            }
            if (sum >= target) {
                return true;
            }
        }
        return false;
    }

    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length, mid;
        while (l + 1 < r) {
            set.clear();
            mid = l + (r - l) / 2;
            if (check(nums, mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }
}
